package com.leetcode.union_find;

/**
 * @author Dennis Li
 * @date 2020/7/28 21:08
 */
public class RedundantConnection_684 {

    public int[] findRedundantConnection(int[][] edges) {
        UF uf = new UF(edges.length);
        int[] ans = new int[2];
        for (int[] edge : edges) {
            if (!uf.connected(edge[0], edge[1]))
                uf.union(edge[0], edge[1]);
            else {
                ans[0] = edge[0];
                ans[1] = edge[1];
            }
        }
        return ans;
    }

    private class UF {
        private int[] id;

        UF(int N) {
            id = new int[N + 1];
            for (int i = 0; i < id.length; i++)
                id[i] = i;
        }

        void union(int u, int v) {
            int uID = find(u);
            // 表明有公共顶点
            int vID = find(v);
            if (uID == vID) return;
            for (int i = 0; i < id.length; i++) {
                if (id[i] == uID) id[i] = vID;
            }
        }

        int find(int p) {
            return id[p];
        }

        boolean connected(int u, int v) {
            return find(u) == find(v);
        }
    }


}
